package com.leetcodehot.problems;

public class problems1092 {
    /**
     * 1092题提供了一个新思路，如果出现内存溢出可以让memo不需要存String，而是存int，我们只需要在构造过程根据memo来判断之前是什么情况就可以继续构造。
     * 1092题最终优化成f二维函数用来记录之前出现过的情况，然后递归构造字符串修改为循环构造字符串（因为f存在已经知道所有的情况了）。
     */

    /**
     * 从最后开始考虑，如果不同，肯定是要新增的
     * 若对s1进行新增，那最终返回值里面 要加上当前s2对应的
     * 若对s2进行新增，那最终返回值加上s1当前对应的
     * 如果两个本来相同那么就继续
     * 会超时
     */
    /*
    public String shortestCommonSupersequence(String str1, String str2) {
        if (str1.isEmpty()) {
            return str2;
        }
        if (str2.isEmpty()) {
            return str1;
        }
        String substring1 = str1.substring(0, str1.length() - 1);
        String substring2 = str2.substring(0, str2.length() - 1);
        char x = str1.charAt(str1.length() - 1);
        char y = str2.charAt(str2.length() - 1);
        if (x == y) {
            return shortestCommonSupersequence(substring1, substring2) + x;
        }
        String ans1 = shortestCommonSupersequence(substring1, str2);
        String ans2 = shortestCommonSupersequence(str1, substring2);
        if (ans1.length() < ans2.length()) {
            return ans1 + x;
        }
        return ans2 + y;
    }
     */

    /**
     * 记忆化搜索优化
     * 会超内存 所以需要优化成不需要保存String
     */
    /*
    private String s, t;
    private String[][] memo;

    public String shortestCommonSupersequence(String str1, String str2) {
        s = str1;
        t = str2;
        memo = new String[s.length() + 1][t.length() + 1];
        return dfs(s.length() - 1, t.length() - 1);
    }

    private String dfs(int i, int j) {
        if (i < 0) {
            return t.substring(0, j + 1);
        }
        if (j < 0) {
            return s.substring(0, i + 1);
        }
        if (memo[i][j] != null) return memo[i][j];
        if (s.charAt(i) == t.charAt(j)) {
            return memo[i][j] = dfs(i - 1, j - 1) + s.charAt(i);
        }
        String ans1 = dfs(i - 1, j);
        String ans2 = dfs(i, j - 1);
        if (ans1.length() < ans2.length()) {
            return memo[i][j] = ans1 + s.charAt(i);
        }
        return memo[i][j] = ans2 + t.charAt(j);
    }
    */
    /**
     * memo存int
     */
    /*
    private String s, t;
    private int[][] memo;

    public String shortestCommonSupersequence(String str1, String str2) {
        s = str1;
        t = str2;
        memo = new int[s.length() + 1][t.length() + 1];
        return makeAns(s.length() - 1, t.length() - 1);
    }

    private int dfs(int i, int j) {
        if (i < 0) {
            return j + 1;
        }
        if (j < 0) {
            return i + 1;
        }
        if (memo[i][j] > 0) return memo[i][j];
        if (s.charAt(i) == t.charAt(j)) {
            return memo[i][j] = dfs(i - 1, j - 1) + 1;
        }
        return memo[i][j] = Math.min(dfs(i - 1, j), dfs(i, j - 1)) + 1;
    }

    private String makeAns(int i, int j) {
        if (i < 0) {
            return t.substring(0, j + 1);
        }
        if (j < 0) {
            return s.substring(0, i + 1);
        }
        if (s.charAt(i) == t.charAt(j)) {
            return makeAns(i - 1, j - 1) + s.charAt(i);
        }
        if (dfs(i, j) == dfs(i - 1, j) + 1) {
            return makeAns(i - 1, j) + s.charAt(i);
        }
        return makeAns(i, j - 1) + t.charAt(j);
    }
    */

    /**
     * 递归改递推
     * 并且makeAns改为循环
     */
    private String s, t;

    public String shortestCommonSupersequence(String str1, String str2) {
        char[] s = str1.toCharArray();
        char[] t = str2.toCharArray();
        int n = s.length;
        int m = t.length;
        int[][] f = new int[n + 1][m + 1];
        for (int j = 1; j <= m; j++) {
            f[0][j] = j;
        }
        for (int i = 1; i <= n; i++) {
            f[i][0] = i;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s[i] == t[j]) {
                    f[i + 1][j + 1] = f[i][j] + 1;
                } else {
                    f[i + 1][j + 1] = Math.min(f[i][j + 1], f[i + 1][j]) + 1;
                }
            }
        }
        int na = f[n][m];
        char[] ans = new char[na];
        for (int i = n - 1, j = m - 1, k = na - 1; ; ) {
            if (i < 0) {
                System.arraycopy(t, 0, ans, 0, j + 1);
                break;
            }
            if (j < 0) {
                System.arraycopy(s, 0, ans, 0, i + 1);
                break;
            }
            if (s[i] == t[j]) {
                ans[k--] = s[i--];
                j--;
            } else if (f[i + 1][j + 1] == f[i][j + 1] + 1) {
                ans[k--] = s[i--];
            } else {
                ans[k--] = t[j--];
            }
        }
        return new String(ans);
    }
}
